package main

import (
	"fmt"
	"sort"
)

/*
 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0
请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]
*/

//自己想的
/*
func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	if len(nums) <= 2 {
		return nil
	}
	var res [][]int
	var i, j int
	for i = 0; i < len(nums); i++ {
		for j = i + 1; j < len(nums); j++ {
			l, r := j+1, len(nums)-1
			for l <= r {
				mid := (l + r) / 2
				if nums[i]+nums[j]+nums[mid] > 0 {
					r = mid - 1
				} else if nums[i]+nums[j]+nums[mid] < 0 {
					l = mid + 1
				} else {
					res = append(res, []int{nums[i], nums[j], nums[mid]})
					break
				}
			}
		}
	}
	//return unique(res)
}
*/

/*
func unique(res [][]int) [][]int {
	var result [][]int
	for _, i := range res {
		flag := true
		for _, j := range result {
			if equal(i, j) {
				flag = false
				break
			}
		}
		if flag {
			result = append(result, i)
		}
	}
	return result
}

func equal(a, b []int) bool {
	for i := 0; i < len(a); i++ {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}
*/

//别人的
func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var res [][]int
	for i := 0; i < len(nums)-2; i++ {
		n1 := nums[i] //固定一个数字
		if n1 > 0 {
			break
		}
		if i > 0 && n1 == nums[i-1] { //如果n[i]和n[i-1]相同 进行下一次循环
			continue
		}
		l, r := i+1, len(nums)-1 //双指针
		for l < r {
			n2, n3 := nums[l], nums[r] //双指针分别为另外两个数字
			if n1+n2+n3 == 0 {
				res = append(res, []int{n1, n2, n3})
				for l < r && nums[l] == n2 { //左指针一直增加 直到n[l] != n[l+1] 为了去重
					l++
				}
				for l < r && nums[r] == n3 { //同理
					r--
				}
			} else if n1+n2+n3 < 0 {
				l++
			} else {
				r--
			}
		}
	}
	return res
}

func main() {
	nums := []int{0, 0, 0, 0}
	fmt.Println(threeSum(nums))
}
